翻訳と辞書
Words near each other
・ "O" Is for Outlaw
・ "O"-Jung.Ban.Hap.
・ "Ode-to-Napoleon" hexachord
・ "Oh Yeah!" Live
・ "Our Contemporary" regional art exhibition (Leningrad, 1975)
・ "P" Is for Peril
・ "Pimpernel" Smith
・ "Polish death camp" controversy
・ "Pro knigi" ("About books")
・ "Prosopa" Greek Television Awards
・ "Pussy Cats" Starring the Walkmen
・ "Q" Is for Quarry
・ "R" Is for Ricochet
・ "R" The King (2016 film)
・ "Rags" Ragland
・ ! (album)
・ ! (disambiguation)
・ !!
・ !!!
・ !!! (album)
・ !!Destroy-Oh-Boy!!
・ !Action Pact!
・ !Arriba! La Pachanga
・ !Hero
・ !Hero (album)
・ !Kung language
・ !Oka Tokat
・ !PAUS3
・ !T.O.O.H.!
・ !Women Art Revolution


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Network (mathematics) : ウィキペディア英語版
Flow network
In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations research, a directed graph is called a network. The vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming flow. A network can be used to model traffic in a road system, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes.
==Definition==

Let G = (V,E) be a finite directed graph in
which every edge (u,v) \in E has a non-negative, real-valued capacity c(u,v). If (u, v) \not \in E, we assume that c(u, v) = 0. We distinguish two vertices: a source and a sink . A flow in a flow network is a real function f:V \times V \rightarrow \mathbb with the following three properties for all nodes and :
;Capacity constraints: f(u,v) \le c(u,v). The flow along an edge cannot exceed its capacity.
;Skew symmetry: f(u,v) = - f(v,u). The net flow from to must be the opposite of the net flow from to (see example).
;Flow conservation: \sum_ f(u,w) = 0, unless u=s or u=t. The net flow to a node is zero, except for the source, which "produces" flow, and the sink, which "consumes" flow.
i.e. Flow conservation implies: \sum_ f(u,v) = \sum_ f(v,z) , for each vertex f(s,v)
The residual capacity of an edge is c_f(u,v) = c(u,v) - f(u,v). This defines a residual network denoted G_f(V,E_f), giving the amount of ''available'' capacity. See that there can be a path from to in the residual network, even though there is no path from to in the original network. Since flows in opposite directions cancel out, ''decreasing'' the flow from to is the same as ''increasing'' the flow from to . An augmenting path is a path (u_1,u_2,\dots,u_k) in the residual network, where u_1=s, u_k=t, and c_f(u_i, u_) > 0. A network is at maximum flow if and only if there is no augmenting path in the residual network G_f .
So G_f is constructed using graph as follows:
# Vertices of G_f = V
# Edges of G_f = E_f defined as-
For each edge (x,y) \in E
# If f(x,y) < c(x,y), make Forward edge (x,y) \in E_f with capacity c_f = c(x,y) - f(x,y) .
# If f(x,y) > 0, make Backward edge (y, x) \in E_f with capacity c_f = f(x,y) .
This concept is used in Ford–Fulkerson algorithm which computes the maximum flow in a flow network.
Sometimes one needs to model a network with more than one source, a supersource is introduced to the graph. This consists of a vertex connected to each of the sources with edges of infinite capacity, so as to act as a global source. A similar construct for sinks is called a supersink.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Flow network」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.